package ren.colorful.learnJava.datastructure;

/**
 * 8皇后问题
 */
public class Queue8Test {
    private int[] result = new int[8]; //棋盘

    public static void main(String[] args) {
        Queue8Test t = new Queue8Test();
        t.call8queues(0);
    }

    public void call8queues(int row){
        if(row == 8){
            //棋盘已经放到了最后一行
            printQueue(result);//打印结果
            return;
        }

        for(int column = 0; column < 8 ; column ++){//每一行都有8种放法
            if(isOk(row,column)){//考察当前格是否满足要求
                result[row] = column;
                call8queues(row + 1); //考察下一行
            }
        }
    }

    private boolean isOk(int row, int column) {
        int leftUp = column - 1,rightUp = column + 1;
        for(int i = row - 1; i >= 0; i --){//逐行往上考察每一行
            if(result[i] == column) return false; // 第i行的column列有棋子吗
            if(leftUp >= 0){
                if(result[i] == leftUp) return false;//左对角线有棋子吗
            }
            if(rightUp < 8){
                if(result[i] == rightUp) return false;//右对角线有棋子吗
            }
            --leftUp; ++rightUp;
        }
        return true;
    }

    private void printQueue(int[] result) { //打印出一个二维矩阵
        for(int row = 0; row < 8 ; ++ row){
            for(int column = 0; column < 8 ; ++ column){
                if(result[row] == column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
